package algorithm.sort;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;

import algorithm.search.SearchSYT;

public class SortSYT {
	
	
	public void printArr(int[] a){
		String s = "\n";
		for(int i = 0; i < a.length; i++){
			s  = s + " " + a[i];
		}
		System.out.println(s);
	}
	
	public void printArr(int[] a , int s, int e){
		String ss = "\n";
		for(int i = s; i <= e; i++){
			ss  = ss + " " + a[i];
		}
		System.out.println(ss);
	}
	
	public boolean insertionSort(int a[]) {
		if(a == null){
			System.out.println("NULL");
			return false;
		}
		if(a.length == 1){
			System.out.println(a[0]);
			return true;
		}
		
		NodeSYT nodeHeadSYT = new NodeSYT(null,a[0]);
		NodeSYT nodeInsertSYT;
		NodeSYT nodeLoopSYT;
		boolean isFind=false;
		for(int i = 1; i < a.length; i++){
			System.out.println("\n");
			nodeHeadSYT.printValue();
			
			nodeLoopSYT = nodeHeadSYT;
			int insertValue = a[i];
			nodeInsertSYT = new NodeSYT(null,insertValue);
			int headValue = nodeHeadSYT.getValue();
			isFind = false;
			if(headValue >= insertValue){
				nodeHeadSYT.insertNodeBefore(nodeInsertSYT);
				nodeHeadSYT = nodeInsertSYT;
			}else{
				while(nodeLoopSYT.getNextNode() != null){
					nodeLoopSYT = nodeLoopSYT.getNextNode();
					if(nodeLoopSYT.getValue() >= insertValue){
						nodeLoopSYT.insertNodeBefore(nodeInsertSYT);
						isFind = true;
						break;
					}
				}
				if(!isFind){
					nodeLoopSYT.insertNodeAfter(nodeInsertSYT);
				}
			}
		}
		System.out.println("\n");
		nodeHeadSYT.printValue();
		return true;
	}
	
	public void insertionSortCorrect(int a[]) {
		printArr(a);
		if(a != null){
			if(a.length >= 1){
				int[] r = a.clone();
				for(int i = 1; i < a.length; i++){
					int j = i;
					a[j] = r[j];
					while(j > 0 && a[j-1] > a[j]){
						int temp = a[j-1];
						a[j-1] = a[j];
						a[j] = temp;
						j--;
					}
					printArr(a);
				}
			}
		}else{
			//TODO
		}
	}
	
	
	public void mergeSort(int[] a, int s, int r, int e){
//		System.out.println("\n s-r:");
//		printArr(a,s,r);
//		System.out.println("\n r-e");
//		printArr(a,r+1,e);
		
		int n1 = r - s + 1;
		int n2 = e - r;
		if(n1 > 1){
			mergeSort(a,s,(s+r)/2,r);
		}
		if(n2 > 1){
			mergeSort(a,r+1,(r+e)/2,e);
		}
	//	printArr(a);
		int[] kArr = new int[n1 + 1];
		for(int i = 0; i < n1; i++){
			kArr[i] = a[s + i];
		}
		kArr[n1] = Integer.MAX_VALUE;
		int[] lArr = new int[n2 + 1];
		for(int i = 0; i < n2; i++){
			lArr[i] = a[r + 1 + i];
		}
		lArr[n2] = Integer.MAX_VALUE;
		int k = 0;
		int l = 0;
		for(int i = s; i <= e; i++){
			if(kArr[k] < lArr[l]){
				a[i] = kArr[k];
				k++;
			}else{
				a[i] = lArr[l];
				l++;
			}
		}
		printArr(a);
	}
	
	
	
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		SortSYT sort = new SortSYT();
		int[] a = new int[100];
		Random random = new Random();
		for(int i = 0; i< 100; i++){
			a[i] = random.nextInt(100);
		}
		sort.mergeSort(a, 0, 50, 99);
		sort.printArr(a);
	}
	
	private class NodeSYT{
		private NodeSYT preNode;
		private int value;
		private NodeSYT nextNode;
		
		public NodeSYT(NodeSYT preNode,int value){
			this.preNode = preNode;
			this.value = value;
		}

		public NodeSYT getPreNode() {
			return preNode;
		}

		public void setPreNode(NodeSYT preNode) {
			this.preNode = preNode;
		}

		public int getValue() {
			return value;
		}

		public void setValue(int value) {
			this.value = value;
		}

		public NodeSYT getNextNode() {
			return nextNode;
		}

		public void setNextNode(NodeSYT nextNode) {
			this.nextNode = nextNode;
		}
		
		public void remove(){
			if(nextNode != null){
				nextNode.preNode = preNode;
			}
			if(preNode != null){
				preNode.nextNode = nextNode;
			}
			preNode = null;
			nextNode = null;
		}
		public void insertNodeBefore(NodeSYT nodeSYT){
			if(preNode != null){
				preNode.setNextNode(nodeSYT);
				nodeSYT.setPreNode(preNode);
			}
			this.setPreNode(nodeSYT);
			nodeSYT.setNextNode(this);
		}
		public void insertNodeAfter(NodeSYT nodeSYT){
			if(nextNode != null){
				nodeSYT.setNextNode(nextNode);
				nextNode.setPreNode(nodeSYT);
			}
			nodeSYT.setPreNode(this);
			this.setNextNode(nodeSYT);
		}
		
		public void printValue(){
			System.out.print(value + " ");
			if(nextNode != null){
				nextNode.printValue();
			}
		}
	}
}

